/*
 * @lc app=leetcode.cn id=134 lang=cpp
 *
 * [134] 加油站
 */

// @lc code=start
class Solution
{
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
    {
        //加油站问题
        //找出可以循环一圈的加油站起点
        //首先计算出每个加油站的剩余量 然后从0开始加 如果<0说明这个区间都不行
        //因为如果能转一圈，那么这一圈任意一段都是>=0
        //如果整段加起来都小于0 那么一定不可能完成
        int cur = 0;   //当前剩余油量
        int total = 0; //总剩余油量
        int start = 0; //开始位置
        for (int i = 0; i < gas.size(); i++)
        {
            cur += gas[i] - cost[i];
            total += gas[i] - cost[i];
            if (cur < 0)
            {
                start = i + 1; //之前那一段都不可以
                cur = 0;
            }
        }
        if (total < 0)
        {
            return -1;
        }
        //因为total>=0说明可以走完一圈 而循环没有修改start说明到结束循环时没问题
        return start;
    }
};
// @lc code=end
